package cn.huyanbing.middleware.sentinel.arithmetic;

import java.time.LocalTime;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

/**
 * @BelongProject middleware
 * @BelongPackage cn.huyanbing.middleware.sentinel.arithmetic
 * @Description
 *  滑动窗口算法(Sliding Window)出现于网络协议中传输层，是一种流量控制技术。我们这里对计数器(固定窗口)算法的临界问题，滑动窗口算法进行了改进，不再固定窗口大小，而是将把固定窗口近一步划分成多个小周期，每个周期都记录自己的请求访问次数，随着时间流逝，滑动时间窗口(每次向后移动一周期)，
 *  同时删除过期的小周期。每次判断限流时，需要将一个窗口的所有小周期合起来，再与阈值进行比较
 * 参考：https://mp.weixin.qq.com/s/2G1Rlhic9M0zTzewb3rRfQ
 * @ClassName MySlidingWindowRateLimiterDemo
 * @Author huyangbing
 * @Date 2024/8/24 07:31
 * @Version 1.0.0
 */
public class MySlidingWindowRateLimiterDemo {

    /** 队列id和队列的映射关系，队列里面存储的是每一次通过时候的时间戳，这样可以使得程序里有多个限流队列 */
    private volatile static Map<String, List<Long>> MAP = new ConcurrentHashMap<>();

    //阈值
    private static int QPS = 2;
    //时间窗口总大小（毫秒）
    private static long WindowSize = 10 * 1000;


    /**
     * 滑动时间窗口限流算法
     * 在指定时间窗口，指定限制次数内，是否允许通过
     *
     * @param listId     队列id
     * @param count      限制次数
     * @param timeWindow 时间窗口大小
     * @return 是否允许通过
     */
    public static synchronized boolean tryAcquire(String listId, int count, long timeWindow) {
        // 获取当前时间
        long nowTime = System.currentTimeMillis();
        // 根据队列id，取出对应的限流队列，若没有则创建
        List<Long> list = MAP.computeIfAbsent(listId, k -> new LinkedList<>());
        // 如果队列还没满，则允许通过，并添加当前时间戳到队列开始位置
        if (list.size() < count) {
            list.add(0, nowTime);
            return true;
        }

        // 队列已满（达到限制次数），则获取队列中最早添加的时间戳
        Long farTime = list.get(count - 1);
        // 用当前时间戳 减去 最早添加的时间戳
        if (nowTime - farTime <= timeWindow) {
            // 若结果小于等于timeWindow，则说明在timeWindow内，通过的次数大于count
            // 不允许通过
            return false;
        } else {
            // 若结果大于timeWindow，则说明在timeWindow内，通过的次数小于等于count
            // 允许通过，并删除最早添加的时间戳，将当前时间添加到队列开始位置
            list.remove(count - 1);
            list.add(0, nowTime);
            return true;
        }
    }

    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i < 20; i++) {
            Thread.sleep(1000);
            LocalTime now = LocalTime.now();
            if (!tryAcquire("ip", QPS, WindowSize)) {// 任意10秒内，只允许2次通过;自定义限流规则“ip”
                System.out.println(now + " 请求被限流");
            } else {
                System.out.println(now + " 请求通过");
            }
        }
    }
}